public class Solution2 {
    //根据一棵树的中序遍历与后序遍历构造二叉树
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


        public int i = 0;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            i = postorder.length - 1;
            return buildTreeChild(postorder,inorder,0,inorder.length-1);
        }
        public TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend) {
            if(inbegin > inend) {
                return null;
            }
            TreeNode root = new TreeNode(postorder[i]);
            //找到当前根在中序遍历的位置
            int rootIndex = findIndex(inorder,inbegin,inend,postorder[i]);
            i--;
            root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
            root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
            return root;
        }
        private int findIndex(int[] inorder,int inbegin, int inend,int key) {
            for(int i = inbegin; i <= inend; i++) {
                if(inorder[i] == key) {
                    return i;
                }
            }
            return -1;
        }
}

